package com.mxw.算法之美.a6排序;

/**
 * @author Administrator
 * @create 2024/7/24 14:46
 */
public class a02InsertionSort {

    /**
      已排序区间和未排序区间，初始已排序区间只有开头第一个元素，取未排序区间的第一个元素，在已排序区间中找到合适的位置插入，并保证已排序区间一直有序。
      4|56123->45|6123->456|123->1456|23->12456|3->123456

     原地排序：空间复杂度O(1)
     稳定排序：相同大小的数据在排序前后不会改变顺序
     时间复杂度：最坏O(n^2) 最好O(n)
     */

    public void insertionSort(int[] a) {
        int n = a.length;
        // 第一个元素是已排序区间
        for (int i = 1; i < n; i++) {
            int value = a[i];
            int j = i - 1;
            // 查找插入的位置
            for (; j >= 0; j--) {
                if (a[j] > value) {
                    // 数据移动
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            // 插入数据
            a[j + 1] = value;
        }
    }
}

